package java_class;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 八皇后问题
 */
public class demo005 {
    public static void main(String[] arge){
        demo005 thisClass = new demo005();
        thisClass.setChess(0, 0);
        // 棋盘
        String[][] checkerboard = new String[8][8];
        // 展示输出
        for (int i = 0; i < thisClass.arrChess.length; i++) {
            checkerboard[thisClass.arrChess[i].x][thisClass.arrChess[i].y] = "●";
//            ○
//            System.out.println("x:"+thisClass.arrChess[i].x+",y:"+thisClass.arrChess[i].y);
        }
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if(null == checkerboard[i][j]){
                    System.out.print("○");
                }else {
                    System.out.print(checkerboard[i][j]);
                }
            }
            System.out.print("\n");
        }
    }
    // 放置棋子(num:放置第N个棋子)
    public boolean setChess(int num, int setIndex){
        // 8个棋子全部放完
        if(num >= 8){
            return true;
        }
        for (int i = setIndex; i < 8 * 8; i++) {
            int x = i % 8; // 判断位置X
            int y = i / 8; // 判断位置Y
            // 新棋子
            Chess newChess = new Chess(x,y);
            // 判断新棋子是否可以放置
            if(!newChess.checkArr(num)) continue;

            // 放置棋子并判断下一棋子
            arrChess[num] = newChess;
            if(setChess(num+1, setIndex+1)){
                if(num == 1){
                    // 全保存
                    List<Chess> tempChess = new ArrayList<>();
                    Collections.addAll(tempChess,arrChess);
                    listChess.add(tempChess);
                }else {
                    return true;
                }
            }
        }
        return false;
    }
    List<List<Chess>> listChess = new ArrayList<>();
    // 已放置棋子
    Chess[] arrChess = new Chess[8];
    // 棋子
    class Chess{
        public int x,y;
        Chess(int x,int y){this.x = x;this.y = y;}
        // 判断棋子是否重叠
        boolean check(Chess obj){
            if(obj.x == this.x) return false; // 同行
            if(obj.y == this.y) return false; // 同列
            if(obj.x - obj.y == this.x - this.y) return false; // 斜线
            return true;
        }
        boolean checkArr(int num){
            for (int j = 0; j < num; j++) {
                if(!arrChess[j].check(this)) return false;
            }
            return true;
        }
    }
}
